#include "util.h"
#include "common_sort.h"

/*
选择排序时间复杂度

T(n) = (n-1)+(n-2)+...+2+1
	 = (n-1)*n/2
	 = O(n^2)

*/

void SelectionSort::sort(std::vector<int>& vec) {
	int len = vec.size();
	for (int i = 0; i < len; ++i) {
		int min = i;
		for (int j = i + 1; j < len; ++j) {
			if (vec[j] < vec[min]) {
				min = j;
			}
		}

		if (min != i) {
			util::swap(vec, i, min);
		}
	}
}

